// 希尔排序是先粗分组 排序 然后越来越细， 最后一次的排序过去了之后肯定是有序的 ，问题是它是怎么缩减时间复杂度的

function shellSort(arr) {
    const n = arr.length 
    let gap = n >> 1
    while(gap) {
        for (let  i = 0 ;i < gap;i++){
                    // 这是冒泡排序吧 
            // 不过这里为什么从 i + gap 开始 而不是i 因为冒泡排序也是直接从第二位开始啊
         /*         for(let j = i+ gap;j < n;j +=gap){
                let temp =j ;
                while( temp > i && arr[temp] < arr[temp - gap]) {
                    swap(arr, temp, temp - gap)
                    temp -= gap
                }
            } 
            */
            // 如果用插入排序 把元素 i和它前面的当做有序数组  从i+ gap开始 ， 
            for (let j = i+ gap; j < n;j+=gap){
                let next = arr[j]
                let tmp = j 
                // while 在执行之前会执行一次条件
                while(tmp){
                    tmp-= gap 
                    if(arr[tmp] > next){
                        arr[tmp + gap] = arr[tmp]
                    }else {
                        arr[tmp +gap] = next
                    break ;
                    }
                }
                // 如果next应该放在头部， 前面的循环会漏掉
                if (next < arr[i]) { arr[i] = next}
            }

        }
        gap >>=1
    }

}


function swap(arr, i, j){
  [arr[i], arr[j]] = [arr[j], arr[i]]
}


function getRandArr(n) {
    const arr = []
    for (let i = 0; i < n; i++) {

        arr.push(Math.random() * 10 * n | 0);
    }
    return arr

}

let  nums = getRandArr(10) ;
let nums2 = [...nums];
nums2.sort((a,b)=> a-b)
console.log(nums2);
shellSort(nums)
console.log(nums);
